package algorithm.backtrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 回溯算法
 */
public class BackTracking {

    /**
     * 全排列组合问题
     */
    @Test
    public void test1() {
        int[] src = {1, 2, 3, 4};
        boolean[] flags = {false, false, false, false};
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dobacktracking(src, flags, path, res);
        System.out.println(res.size());
        for (List<Integer> re : res) {
            for (Integer integer : re) {
                System.out.print(integer + "-");
            }
            System.out.println();
        }
    }

    public void dobacktracking(int[] src, boolean[] flags, List<Integer> path, List<List<Integer>> res) {
        //如果 flags 全是true，代表到头了
        boolean flagsAllTrue = true;
        for (boolean flag : flags) {
            if (!flag) flagsAllTrue = false;
        }
        if (flagsAllTrue) {
            List<Integer> r = new ArrayList<>();
            for (Integer p : path) {
                r.add(p);
            }
            res.add(r);
            return;
        }
        for (int i = 0; i < src.length; i++) {
            if (flags[i]) continue;
            int curEle = src[i];
            flags[i] = true;
            path.add(curEle);
            dobacktracking(src, flags, path, res);
            path.remove(path.size() - 1);
            flags[i] = false;
        }
    }

    /**
     * 子集
     */
    @Test
    public void test2() {
        int[] src = {1, 2, 3, 4};
        int startIdx = 0;
        ArrayList<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        dobacktracking(src,startIdx, path,res);
        System.out.println(res.size());
        for (List<Integer> re : res) {
            for (Integer integer : re) {
                System.out.print(integer + "-");
            }
            System.out.println();
        }
    }

    /**
     * @param src
     * @param startIdx 从下标处，开始遍历
     * @param path
     * @param res
     */
    public void dobacktracking(int[] src, int startIdx, List<Integer> path, List<List<Integer>> res) {
        //TODO 20240201 这个可以删除,如果 startIndex 到达最后一个,底下的for 循环不执行
        if (startIdx >= src.length) {
            return;
        }

        //添加子集到 res
        for (int start = startIdx; start < src.length; start++) {
            int curEle = src[start];
            path.add(curEle);
            /*
             TODO 20240201 这个可以放到开头
             记录路径
             注意：全排列 是在递归终结的地方记录。子集是在路径
             */
            List<Integer> r = new ArrayList<Integer>();
            for (Integer integer : path) {
                r.add(integer);
            }
            res.add(r);
            dobacktracking(src, start+1, path, res);
            path.remove(path.size() - 1);
        }

    }

    /**
     * 长度为n的子集
     * 涉及到减枝了。
     */
    public void test3() {

    }

}
